/*
 * @Author: liusheng
 * @Date: 2022-04-13 12:21:22
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-13 16:02:32
 * @Description: 剑指 Offer II 027. 回文链表
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 
 剑指 Offer II 027. 回文链表
给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

 

示例 1：



输入: head = [1,2,3,3,2,1]
输出: true
示例 2：



输入: head = [1,2]
输出: false
 

提示：

链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9
 

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

 

注意：本题与主站 234 题相同：https://leetcode-cn.com/problems/palindrome-linked-list/
 */

struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next)
        {
            return true;
        }

        ListNode * pMiddle = findMiddleInList(head);
        //the second half part begin
        ListNode * p2 = pMiddle->next;
        //split the list into two
        pMiddle->next = nullptr;

        ListNode * p1 = head;

        //reverse the second half,not first half
        //because node num can be odd
        p2 = reverseList(p2);

        while (p1 && p2)
        {
            if (p1->val != p2->val)
            {
                return false;
            }

            p1 = p1->next;
            p2 = p2->next;
        }

        return true;
    }
    
private:
    ListNode * reverseList(ListNode * head)
    {
        if (!head || !head->next)
        {
            return head;
        }
        ListNode * pre = nullptr;
        ListNode * cur = head;
        while (cur)
        {
            ListNode * curNext = cur->next;
            cur->next = pre;
            
            pre = cur;
            cur = curNext;
        }

        return pre;
    }
    ListNode * findMiddleInList(ListNode * head)
    {
        if (!head || !head->next)
        {
            return head;
        }

        ListNode * slow = head;
        ListNode * fast = head;

        while (fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

//recursive solution
class Solution2 {
public:
    bool isPalindrome(ListNode* head) {
        front = head;
        return recursiveCheck(head);
    }
private:
    //recurseive solution,back point go to the last one,then back 
    //step 1 to the front,front from head go to last
    bool recursiveCheck(ListNode * back)
    {
        if (back != nullptr)
        {
            if (!recursiveCheck(back->next))
            {
                return false;
            }

            // printf("front value:%d,back value:%d\n",front->val,back->val);
            if (front->val != back->val)
            {
                return false;
            }
            //after compare current value,front go to next
            //the recursive will auto make back to the front by one step
            front = front->next;
        }
        return true;
    }

    ListNode * front;
};